{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Ways to Wear Different Hats to Each Other"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #dynamic-programming #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #动态规划 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberWays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #每个人戴不同帽子的方案数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>总共有 <code>n</code>&nbsp;个人和 <code>40</code> 种不同的帽子，帽子编号从 <code>1</code> 到 <code>40</code> 。</p>\n",
    "\n",
    "<p>给你一个整数列表的列表&nbsp;<code>hats</code>&nbsp;，其中&nbsp;<code>hats[i]</code>&nbsp;是第 <code>i</code>&nbsp;个人所有喜欢帽子的列表。</p>\n",
    "\n",
    "<p>请你给每个人安排一顶他喜欢的帽子，确保每个人戴的帽子跟别人都不一样，并返回方案数。</p>\n",
    "\n",
    "<p>由于答案可能很大，请返回它对&nbsp;<code>10^9 + 7</code>&nbsp;取余后的结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>hats = [[3,4],[4,5],[5]]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>给定条件下只有一种方法选择帽子。\n",
    "第一个人选择帽子 3，第二个人选择帽子 4，最后一个人选择帽子 5。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>hats = [[3,5,1],[3,5]]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>总共有 4 种安排帽子的方法：\n",
    "(3,5)，(5,3)，(1,3) 和 (1,5)\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]]\n",
    "<strong>输出：</strong>24\n",
    "<strong>解释：</strong>每个人都可以从编号为 1 到 4 的帽子中选。\n",
    "(1,2,3,4) 4 个帽子的排列方案数为 24 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>hats = [[1,2,3],[2,3,5,6],[1,3,7,9],[1,8,9],[2,5,7]]\n",
    "<strong>输出：</strong>111\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == hats.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10</code></li>\n",
    "\t<li><code>1 &lt;= hats[i].length &lt;= 40</code></li>\n",
    "\t<li><code>1 &lt;= hats[i][j] &lt;= 40</code></li>\n",
    "\t<li><code>hats[i]</code>&nbsp;包含一个数字互不相同的整数列表。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-ways-to-wear-different-hats-to-each-other](https://leetcode.cn/problems/number-of-ways-to-wear-different-hats-to-each-other/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-ways-to-wear-different-hats-to-each-other](https://leetcode.cn/problems/number-of-ways-to-wear-different-hats-to-each-other/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[3,4],[4,5],[5]]', '[[3,5,1],[3,5]]', '[[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        n = len(hats)\n",
    "        m = 1 << n\n",
    "        people = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for h in hats[i]:\n",
    "                people[h].append(i)\n",
    "        dp = [0] * m\n",
    "        dp[0] = 1\n",
    "        for h in range(1, 41):\n",
    "            for i in range(m - 1, - 1, - 1):\n",
    "                for p in people[h]:\n",
    "                    if i & 1 << p:\n",
    "                        continue \n",
    "                    dp[i | (1 << p)] += dp[i]\n",
    "                    dp[i | (1 << p)] %= 10 ** 9 + 7 \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        n = len(hats)\n",
    "        dp = [0] * (1 << n)\n",
    "        dp[0] = 1  # 初始化状态，没有人拿到帽子的方案数为1\n",
    "        \n",
    "        # 用于快速查找哪些人喜欢某顶帽子\n",
    "        hat_to_people = [[] for _ in range(41)]\n",
    "        for i, hat_list in enumerate(hats):\n",
    "            for h in hat_list:\n",
    "                hat_to_people[h].append(i)\n",
    "        \n",
    "        # 动态规划\n",
    "        for h in range(1, 41):\n",
    "            old_dp = dp[:]\n",
    "            for state in range(1 << n):\n",
    "                # 如果当前状态是dp[state]，更新与它相关的新状态\n",
    "                if old_dp[state] == 0:\n",
    "                    continue\n",
    "                for person in hat_to_people[h]:\n",
    "                    # 如果这个人还没有得到帽子\n",
    "                    if (state >> person) & 1 == 0:\n",
    "                        new_state = state | (1 << person)\n",
    "                        dp[new_state] += old_dp[state]\n",
    "                        dp[new_state] %= MOD\n",
    "                        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        n = len(hats)\n",
    "        dp = [0] * (1 << n)\n",
    "        dp[0] = 1  # 初始化状态，没有人拿到帽子的方案数为1\n",
    "        \n",
    "        # 用于快速查找哪些人喜欢某顶帽子\n",
    "        hat_to_people = [[] for _ in range(41)]\n",
    "        for i, hat_list in enumerate(hats):\n",
    "            for h in hat_list:\n",
    "                hat_to_people[h].append(i)\n",
    "        \n",
    "        # 动态规划\n",
    "        for h in range(1, 41):\n",
    "            old_dp = dp[:]\n",
    "            for state in range(1 << n):\n",
    "                # 如果当前状态是dp[state]，更新与它相关的新状态\n",
    "                if old_dp[state] == 0:\n",
    "                    continue\n",
    "                for person in hat_to_people[h]:\n",
    "                    # 如果这个人还没有得到帽子\n",
    "                    if (state >> person) & 1 == 0:\n",
    "                        new_state = state | (1 << person)\n",
    "                        dp[new_state] += old_dp[state]\n",
    "                        dp[new_state] %= MOD\n",
    "                        \n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        n = len(hats)\n",
    "        m = 1 << n\n",
    "        people = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for h in hats[i]:\n",
    "                people[h].append(i)\n",
    "        dp = [0] * m\n",
    "        dp[0] = 1\n",
    "        for h in range(1, 41):\n",
    "            for i in range(m - 1, - 1, - 1):\n",
    "                for p in people[h]:\n",
    "                    if i & 1 << p:\n",
    "                        continue \n",
    "                    dp[i | (1 << p)] += dp[i]\n",
    "                    dp[i | (1 << p)] %= 10 ** 9 + 7 \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        n = len(hats)\n",
    "        dp = [0] * (1 << n)\n",
    "        dp[0] = 1  # 初始化状态，没有人拿到帽子的方案数为1\n",
    "        \n",
    "        # 用于快速查找哪些人喜欢某顶帽子\n",
    "        hat_to_people = [[] for _ in range(41)]\n",
    "        for i, hat_list in enumerate(hats):\n",
    "            for h in hat_list:\n",
    "                hat_to_people[h].append(i)\n",
    "        \n",
    "        # 动态规划\n",
    "        for h in range(1, 41):\n",
    "            old_dp = dp[:]\n",
    "            for state in range(1 << n):\n",
    "                # 如果当前状态是dp[state]，更新与它相关的新状态\n",
    "                if old_dp[state] == 0:\n",
    "                    continue\n",
    "                for person in hat_to_people[h]:\n",
    "                    # 如果这个人还没有得到帽子\n",
    "                    if (state >> person) & 1 == 0:\n",
    "                        new_state = state | (1 << person)\n",
    "                        dp[new_state] += old_dp[state]\n",
    "                        dp[new_state] %= MOD\n",
    "                        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        n = len(hats)\n",
    "        dp = [0] * (1 << n)\n",
    "        dp[0] = 1  # 初始化状态，没有人拿到帽子的方案数为1\n",
    "        \n",
    "        # 用于快速查找哪些人喜欢某顶帽子\n",
    "        hat_to_people = [[] for _ in range(41)]\n",
    "        for i, hat_list in enumerate(hats):\n",
    "            for h in hat_list:\n",
    "                hat_to_people[h].append(i)\n",
    "        \n",
    "        # 动态规划\n",
    "        for h in range(1, 41):\n",
    "            old_dp = dp[:]\n",
    "            for state in range(1 << n):\n",
    "                # 如果当前状态是dp[state]，更新与它相关的新状态\n",
    "                if old_dp[state] == 0:\n",
    "                    continue\n",
    "                for person in hat_to_people[h]:\n",
    "                    # 如果这个人还没有得到帽子\n",
    "                    if (state >> person) & 1 == 0:\n",
    "                        new_state = state | (1 << person)\n",
    "                        dp[new_state] += old_dp[state]\n",
    "                        dp[new_state] %= MOD\n",
    "                        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        # mod = 10 ** 9 + 7\n",
    "        # n = len(hats)\n",
    "        # f = [defaultdict(int) for _ in range(n)]\n",
    "        # for i in hats[0]:\n",
    "        #     f[0][1<<i] = 1\n",
    "        # for i in range(1, n):\n",
    "        #     for x in hats[i]:\n",
    "        #         for k, v in f[i-1].items():\n",
    "        #             if k & (1 << x) == 0:\n",
    "        #                 f[i][k | (1 << x)] += v\n",
    "        # return sum(f[-1].values()) % mod\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(hats)\n",
    "        maxHatId = max(max(ids) for ids in hats)\n",
    "\n",
    "        hatToPerson = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for h in hats[i]:\n",
    "                hatToPerson[h].append(i)\n",
    "\n",
    "        f = [[0] * (1 << n) for _ in range(maxHatId + 1)]\n",
    "        # 边界条件\n",
    "        f[0][0] = 1\n",
    "        for i in range(1, maxHatId + 1):\n",
    "            for mask in range(1 << n):\n",
    "                f[i][mask] = f[i - 1][mask]\n",
    "                for j in hatToPerson[i]:\n",
    "                    if mask & (1 << j):\n",
    "                        f[i][mask] += f[i - 1][mask ^ (1 << j)]\n",
    "                f[i][mask] %= mod\n",
    "        \n",
    "        return f[maxHatId][(1 << n) - 1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        n = len(hats)\n",
    "        full_mask = (1<<n)\n",
    "\n",
    "        dp = [[0]*full_mask for _ in range(41)]\n",
    "\n",
    "        dp[0][0] = 1\n",
    "\n",
    "        MODX = 10**9+7\n",
    "\n",
    "        for i in range(1,41):\n",
    "            for j in range(full_mask):\n",
    "                if j==0:\n",
    "                    dp[i][j] = 1\n",
    "                    continue \n",
    "                dp[i][j] = dp[i-1][j]\n",
    "\n",
    "                for k in range(n):\n",
    "                    if i in hats[k] and (j & (1<<k) >0):\n",
    "                        dp[i][j] += dp[i-1][j-(1<<k)]\n",
    "                dp[i][j] %= MODX\n",
    "        return dp[40][full_mask-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        hats = [set(h) for h in hats]\n",
    "        n = len(hats)\n",
    "        dp = [[0] * (1 << n) for _ in range(41)]\n",
    "        \"\"\"\n",
    "        dp[i][k] # 选择第i个帽子后，状态k的方案数dp[i][k] = dp[i-1][k] + dp[i-1][k ^ 1 << j]\n",
    "        \"\"\"\n",
    "        for i in range(1, 41):\n",
    "            for j in range(n):\n",
    "                if i in hats[j]:\n",
    "                    dp[i][1 << j] = 1\n",
    "            for k in range(1, 1 << n):\n",
    "                dp[i][k] += dp[i - 1][k]\n",
    "                for j in range(n):\n",
    "                    if k & 1 << j and i in hats[j]:\n",
    "                        dp[i][k] += dp[i - 1][k ^ 1 << j]\n",
    "                        dp[i][k] %= (10 ** 9 + 7)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        n = len(hats)\n",
    "        dp = [[0]*(1 << n) for _ in range(42)]\n",
    "        for i in range(42):\n",
    "            dp[i][(1 << n)-1] = 1\n",
    "        for hatid in range(40, 0, -1):\n",
    "            for mask in range((1 << n)-1):\n",
    "                dp[hatid][mask] = dp[hatid+1][mask]\n",
    "                for i in range(n):\n",
    "                    if not mask & (1 << i) and hatid in hats[i]:\n",
    "                        dp[hatid][mask] += dp[hatid+1][mask | (1 << i)]\n",
    "        return dp[1][0] % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        MOD = 10**9+7\n",
    "        n = len(hats)\n",
    "        maxHatId = max([max(ids) for ids in hats])\n",
    "        hatToPerson = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for h in hats[i]:\n",
    "                hatToPerson[h].append(i)\n",
    "\n",
    "        # f[i][s] 表示处理了前i顶帽子，已经被分配帽子的人的状态是s的方案数\n",
    "        f = [[0]*(1<<n) for _ in range(maxHatId+1)]\n",
    "        f[0][0] = 1\n",
    "        for i in range(1,maxHatId+1):\n",
    "            for s in range(1<<n):\n",
    "                f[i][s] = f[i-1][s]\n",
    "                for j in hatToPerson[i]:\n",
    "                    if s & (1<<j):\n",
    "                        f[i][s] += f[i-1][s^(1<<j)]\n",
    "                f[i][s]%=MOD\n",
    "        return f[maxHatId][(1<<n)-1]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(hats)\n",
    "        # 找到帽子编号的最大值，这样我们只需要求出 $f[maxhatid][2^n - 1]$ 作为答案\n",
    "        maxHatId = max(max(ids) for ids in hats)\n",
    "        \n",
    "        # 对于每一顶帽子 h，hatToPerson[h] 中存储了喜欢这顶帽子的所有人，方便进行动态规划\n",
    "        hatToPerson = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for h in hats[i]:\n",
    "                hatToPerson[h].append(i)\n",
    "        \n",
    "        f = [[0] * (1 << n) for _ in range(maxHatId + 1)]\n",
    "        # 边界条件\n",
    "        f[0][0] = 1\n",
    "        for i in range(1, maxHatId + 1):\n",
    "            for mask in range(1 << n):\n",
    "                f[i][mask] = f[i - 1][mask]\n",
    "                for j in hatToPerson[i]:\n",
    "                    if mask & (1 << j):\n",
    "                        f[i][mask] += f[i - 1][mask ^ (1 << j)]\n",
    "                f[i][mask] %= mod\n",
    "        \n",
    "        return f[maxHatId][(1 << n) - 1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        # 模板：经典状压DP逆向思维，填表法迭代实现\n",
    "        n = len(hats)\n",
    "        people = [[] for _ in range(40)]\n",
    "        for u in range(n):\n",
    "            for v in hats[u]:\n",
    "                people[v - 1].append(u)\n",
    "\n",
    "        dp = [[0] * (1 << n) for _ in range(41)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(40):\n",
    "            for j in range(1 << n):\n",
    "                dp[i + 1][j] = dp[i][j]\n",
    "                for x in people[i]:\n",
    "                    if (1 << x) & j:\n",
    "                        dp[i + 1][j] += dp[i][j ^ (1 << x)]\n",
    "                        dp[i + 1][j] %= mod\n",
    "\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7 \n",
    "        n = len(hats)\n",
    "\n",
    "        maxHatId = max(max(ids) for ids in hats)\n",
    "\n",
    "        hatToPerson = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for h in hats[i]:\n",
    "                hatToPerson[h].append(i)\n",
    "        f = [[0]*(1<<n) for _ in range(maxHatId+1)]\n",
    "\n",
    "        f[0][0] = 1 \n",
    "\n",
    "        for i in range(1,maxHatId+1):\n",
    "            for mask in range(1<<n):\n",
    "                f[i][mask] = f[i-1][mask]\n",
    "                for j in hatToPerson[i]:\n",
    "                    if mask & (1<< j):\n",
    "                        f[i][mask] +=f[i-1][mask^(1<<j)]\n",
    "                f[i][mask] %= mod \n",
    "        return f[maxHatId][(1<<n)-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\r\n",
    "        mod = 1e9+7\r\n",
    "        n = len(hats)\r\n",
    "        f = [[0]*41 for _ in range(1 << n)]\r\n",
    "        exist_dict = {}\r\n",
    "        for i in range(n):\r\n",
    "            for j in hats[i]:\r\n",
    "                exist_dict[(i, j)] = True\r\n",
    "        for i in range(n):\r\n",
    "            val = 1 << i\r\n",
    "            for j in range(1, 41):\r\n",
    "                f[val][j] = f[val][j-1] + int((i, j) in exist_dict)\r\n",
    "        for i in range(1, 1 << n):\r\n",
    "            for j in range(1, 41):\r\n",
    "                if f[i][j]:\r\n",
    "                    continue\r\n",
    "                f[i][j] = (f[i][j] + f[i][j-1]) % mod\r\n",
    "                for k in range(n):\r\n",
    "                    val = 1 << k\r\n",
    "                    if (k, j) in exist_dict and i & val == val:\r\n",
    "                        f[i][j] = (f[i][j] + f[i ^ val][j-1]) % mod\r\n",
    "        return int(f[(1 << n)-1][40])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(hats)\n",
    "        # 找到帽子编号的最大值，这样我们只需要求出 $f[maxhatid][2^n - 1]$ 作为答案\n",
    "        maxHatId = max(max(ids) for ids in hats)\n",
    "        \n",
    "        # 对于每一顶帽子 h，hatToPerson[h] 中存储了喜欢这顶帽子的所有人，方便进行动态规划\n",
    "        hatToPerson = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for h in hats[i]:\n",
    "                hatToPerson[h].append(i)\n",
    "        \n",
    "        f = [[0] * (1 << n) for _ in range(maxHatId + 1)]\n",
    "        # 边界条件\n",
    "        f[0][0] = 1\n",
    "        for i in range(1, maxHatId + 1):\n",
    "            for mask in range(1 << n):\n",
    "                f[i][mask] = f[i - 1][mask]\n",
    "                for j in hatToPerson[i]:\n",
    "                    if mask & (1 << j):\n",
    "                        f[i][mask] += f[i - 1][mask ^ (1 << j)]\n",
    "                f[i][mask] %= mod\n",
    "        \n",
    "        return f[maxHatId][(1 << n) - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(hats)\n",
    "        # 找到帽子编号的最大值，这样我们只需要求出 $f[maxhatid][2^n - 1]$ 作为答案\n",
    "        maxHatId = max(max(ids) for ids in hats)\n",
    "        \n",
    "        # 对于每一顶帽子 h，hatToPerson[h] 中存储了喜欢这顶帽子的所有人，方便进行动态规划\n",
    "        hatToPerson = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for h in hats[i]:\n",
    "                hatToPerson[h].append(i)\n",
    "        \n",
    "        f = [[0] * (1 << n) for _ in range(maxHatId + 1)]\n",
    "        # 边界条件\n",
    "        f[0][0] = 1\n",
    "        for i in range(1, maxHatId + 1):\n",
    "            for mask in range(1 << n):\n",
    "                f[i][mask] = f[i - 1][mask]\n",
    "                for j in hatToPerson[i]:\n",
    "                    if mask & (1 << j):\n",
    "                        f[i][mask] += f[i - 1][mask ^ (1 << j)]\n",
    "                f[i][mask] %= mod\n",
    "        \n",
    "        return f[maxHatId][(1 << n) - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(hats)\n",
    "        # 找到帽子编号的最大值，这样我们只需要求出 $f[maxhatid][2^n - 1]$ 作为答案\n",
    "        maxHatId = max(max(ids) for ids in hats)\n",
    "        \n",
    "        # 对于每一顶帽子 h，hatToPerson[h] 中存储了喜欢这顶帽子的所有人，方便进行动态规划\n",
    "        hatToPerson = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for h in hats[i]:\n",
    "                hatToPerson[h].append(i)\n",
    "        \n",
    "        f = [[0] * (1 << n) for _ in range(maxHatId + 1)]\n",
    "        # 边界条件\n",
    "        f[0][0] = 1\n",
    "        for i in range(1, maxHatId + 1):\n",
    "            for mask in range(1 << n):\n",
    "                f[i][mask] = f[i - 1][mask]\n",
    "                for j in hatToPerson[i]:\n",
    "                    if mask & (1 << j):\n",
    "                        f[i][mask] += f[i - 1][mask ^ (1 << j)]\n",
    "                f[i][mask] %= mod\n",
    "        \n",
    "        return f[maxHatId][(1 << n) - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        dd = 10**9+7\n",
    "        to = [set() for _ in range(41)]\n",
    "        for i, hat in enumerate(hats):\n",
    "            for h in hat:\n",
    "                to[h].add(i)\n",
    "        n = len(hats)\n",
    "        ans = [[0 for _ in range(2**n)] for __ in range(41)]\n",
    "        ans[0][0] = 1\n",
    "        for i in range(1, 41):\n",
    "            for j in range(2**n):\n",
    "                if j == 0:\n",
    "                    ans[i][j] = 1\n",
    "                else:\n",
    "                    for k in range(n):\n",
    "                        if ((1 << k) & j) and k in to[i]:\n",
    "                            ans[i][j] += ans[i-1][j-(1<<k)]\n",
    "                    ans[i][j] += ans[i-1][j]\n",
    "                    ans[i][j] %= dd\n",
    "        return ans[-1][-1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        n = len(hats)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        for i in range(n):\n",
    "            hats[i] = set(hats[i])\n",
    "\n",
    "        #看数据范围，应该是帽子去找人，状压人是否戴帽\n",
    "        # 当前帽子值为j, 所有人是否戴帽的状态为mask\n",
    "        @cache\n",
    "        def dfs(j, mask):\n",
    "            if mask == (1 << n) - 1:\n",
    "                return 1\n",
    "            if j > 40:\n",
    "                return 0\n",
    "            \n",
    "            res = dfs(j + 1, mask) #不戴j这顶帽子\n",
    "            for i in range(n):\n",
    "                if j in hats[i] and mask & (1 << i) == 0:\n",
    "                    res += dfs(j + 1, mask | 1 << i) #给i这个人戴j这顶帽子\n",
    "                    res %= MOD\n",
    "            return res % MOD\n",
    "\n",
    "        res = dfs(1, 0)\n",
    "        del dfs\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        mod=10**9+7\n",
    "        n=len(hats)\n",
    "        \n",
    "        \n",
    "        dicc=defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for j in hats[i]:\n",
    "                dicc[j-1].append(i)\n",
    "        \n",
    "        l=[]\n",
    "        for i in dicc:\n",
    "            l.append((dicc[i],i))\n",
    "        l.sort(key=lambda x:x[1])\n",
    "        \n",
    "        l=[i[0] for i in l]\n",
    "        \n",
    "        # print(dicc)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(mask,pos):\n",
    "            if pos==len(l):\n",
    "                return int(mask==(1<<n)-1)\n",
    "            # if mask==(1<<n)-1:return 1\n",
    "            ans=0\n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            for i in l[pos]:\n",
    "                if (mask>>i)&1:\n",
    "                    continue\n",
    "                ans+=dfs(mask|(1<<i),pos+1)\n",
    "                ans%=mod\n",
    "            \n",
    "            ans+=dfs(mask,pos+1)\n",
    "            return ans%mod\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        return dfs(0,0)%mod\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(hats)\n",
    "        \n",
    "        m = max(max(h) for h in hats)\n",
    "        dct = [0]*(m+1)\n",
    "        for i in range(n):\n",
    "            for j in hats[i]:\n",
    "                dct[j] |= (1<<i)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(x, state):\n",
    "            if not state:\n",
    "                return 1\n",
    "            if x == m+1:\n",
    "                return 0\n",
    "            res = dfs(x+1, state)\n",
    "            for i in range(n):\n",
    "                if state & (1<<i) and dct[x] & (1<<i):\n",
    "                    res += dfs(x+1, state^(1<<i))\n",
    "            return res % mod\n",
    "        \n",
    "        return dfs(0, (1<<n)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        n = len(hats)\n",
    "        states = []\n",
    "        for hs in hats:\n",
    "            state = 0\n",
    "            for h in hs:\n",
    "                state |= 1<<h\n",
    "            states.append(state)\n",
    "\n",
    "        @cache\n",
    "        def dp(i, mask):\n",
    "            nonlocal n\n",
    "            if i == 0:\n",
    "                return int(mask==0)\n",
    "            num = dp(i-1, mask)\n",
    "            for j in range(n):\n",
    "                if (1<<j) & mask != 0 and (1<<i) & states[j] != 0:\n",
    "                    num += dp(i-1, mask^(1<<j))\n",
    "            num %= (10**9+7)\n",
    "            return num\n",
    "        \n",
    "        return dp(40, (1<<n)-1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        # dp[i][j]：现在考虑到第i个帽子，已经获得帽子的状态是j的情况下，分配的方案数是多少\n",
    "        # 因为如果以人为阶段的话，最后一个人考虑选哪个帽子，但是选这个帽子之前，还要考虑这个帽子是否被前面的人选过\n",
    "        # 转移(考虑这个帽子选or不选)\n",
    "        # ret = dfs(i-1,j) + dfs( i-1 , k )    # 其中k是分配完之后的状态\n",
    "        # 边界条件：i==0时，return 1 if j==0 else 0\n",
    "        # 因为要知道这个帽子可以选哪些人，所以要先预处理出数组\n",
    "        n = len(hats)\n",
    "        book = [0] * 41\n",
    "        for i in range(n):\n",
    "            for hat in hats[i]:\n",
    "                book[hat] |= (1<<i)\n",
    "\n",
    "        MOD = 10**9+7\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i==0:\n",
    "                return 1 if j==0 else 0\n",
    "            \n",
    "            ret = dfs(i-1,j)        # 这个帽子不分配\n",
    "            for bit in range(n):\n",
    "                if j&(1<<bit) and book[i]&(1<<bit):       # 如果这个人没被分配，而且这个帽子可以分配给这个人\n",
    "                    ret = ( ret + dfs(i-1,j^(1<<bit)) )%MOD\n",
    "            \n",
    "            return ret\n",
    "        \n",
    "        return dfs(40,(1<<n)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        # dp[i][j]：现在考虑到第i个帽子，已经获得帽子的状态是j的情况下，分配的方案数是多少\n",
    "        # 因为如果以人为阶段的话，最后一个人考虑选哪个帽子，但是选这个帽子之前，还要考虑这个帽子是否被前面的人选过\n",
    "        # 转移(考虑这个帽子选or不选)\n",
    "        # ret = dfs(i-1,j) + dfs( i-1 , k )    # 其中k是分配完之后的状态\n",
    "        # 边界条件：i==0时，return 1 if j==0 else 0\n",
    "        # 因为要知道这个帽子可以选哪些人，所以要先预处理出数组\n",
    "        n = len(hats)\n",
    "        book = [0] * 41\n",
    "        for i in range(n):\n",
    "            for hat in hats[i]:\n",
    "                book[hat] |= (1<<i)\n",
    "\n",
    "        MOD = 10**9+7\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i==0:\n",
    "                return 1 if j==0 else 0\n",
    "            \n",
    "            ret = dfs(i-1,j)        # 这个帽子不分配\n",
    "            for bit in range(n):\n",
    "                if j&(1<<bit) and book[i]&(1<<bit):       # 如果这个人没被分配，而且这个帽子可以分配给这个人\n",
    "                    ret = ( ret + dfs(i-1,j^(1<<bit)) )%MOD\n",
    "            \n",
    "            return ret\n",
    "        \n",
    "        return dfs(40,(1<<n)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        # dp[i][j]：现在考虑到第i个帽子，已经获得帽子的状态是j的情况下，分配的方案数是多少\n",
    "        # 因为如果以人为阶段的话，最后一个人考虑选哪个帽子，但是选这个帽子之前，还要考虑这个帽子是否被前面的人选过\n",
    "        # 转移(考虑这个帽子选or不选)\n",
    "        # ret = dfs(i-1,j) + dfs( i-1 , k )    # 其中k是分配完之后的状态\n",
    "        # 边界条件：i==0时，return 1 if j==0 else 0\n",
    "        # 因为要知道这个帽子可以选哪些人，所以要先预处理出数组\n",
    "        n = len(hats)\n",
    "        book = [0] * 41\n",
    "        for i in range(n):\n",
    "            for hat in hats[i]:\n",
    "                book[hat] |= (1<<i)\n",
    "\n",
    "        MOD = 10**9+7\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i==0:\n",
    "                return 1 if j==0 else 0\n",
    "            \n",
    "            ret = dfs(i-1,j)        # 这个帽子不分配\n",
    "            for bit in range(n):\n",
    "                if j&(1<<bit) and book[i]&(1<<bit):       # 如果这个人没被分配，而且这个帽子可以分配给这个人\n",
    "                    ret = ( ret + dfs(i-1,j^(1<<bit)) )%MOD\n",
    "            \n",
    "            return ret\n",
    "        \n",
    "        return dfs(40,(1<<n)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        # dp[i][j]：现在考虑到第i个帽子，已经获得帽子的状态是j的情况下，分配的方案数是多少\n",
    "        # 因为如果以人为阶段的话，最后一个人考虑选哪个帽子，但是选这个帽子之前，还要考虑这个帽子是否被前面的人选过\n",
    "        # 转移(考虑这个帽子选or不选)\n",
    "        # ret = dfs(i-1,j) + dfs( i-1 , k )    # 其中k是分配完之后的状态\n",
    "        # 边界条件：i==0时，return 1 if j==0 else 0\n",
    "        # 因为要知道这个帽子可以选哪些人，所以要先预处理出数组\n",
    "        n = len(hats)\n",
    "        book = [0] * 41\n",
    "        for i in range(n):\n",
    "            for hat in hats[i]:\n",
    "                book[hat] |= (1<<i)\n",
    "\n",
    "        MOD = 10**9+7\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i==0:\n",
    "                return 1 if j==0 else 0\n",
    "            \n",
    "            ret = dfs(i-1,j)        # 这个帽子不分配\n",
    "            for bit in range(n):\n",
    "                if j&(1<<bit) and book[i]&(1<<bit):       # 如果这个人没被分配，而且这个帽子可以分配给这个人\n",
    "                    ret = ( ret + dfs(i-1,j^(1<<bit)) )%MOD\n",
    "            \n",
    "            return ret\n",
    "        \n",
    "        return dfs(40,(1<<n)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        n = len(hats)\n",
    "        hats = [set(hs) for hs in hats]\n",
    "\n",
    "        @cache\n",
    "        def dp(idx, mask):\n",
    "            if idx == 0:\n",
    "                return int(mask==0)\n",
    "            \n",
    "            num = dp(idx-1, mask)\n",
    "            nonlocal n\n",
    "            for j in range(n):\n",
    "                if mask&(1<<j) != 0 and idx in hats[j]:\n",
    "                    num += dp(idx-1, mask^(1<<j))\n",
    "            \n",
    "            return num%(10**9+7)\n",
    "        \n",
    "        return dp(40, (1<<n)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        @cache\n",
    "        def dfs(cur, u):\n",
    "            if u == m:                \n",
    "                return 1 if cur.bit_count() == n else 0\n",
    "            ans = dfs(cur, u + 1)            \n",
    "            for i in h[u]:\n",
    "                if cur & (1 << i) == 0:\n",
    "                    ans = (ans + dfs(cur | (1 << i), u + 1)) % MOD\n",
    "            return ans\n",
    "\n",
    "        m = 0\n",
    "        seen = dict()\n",
    "        h = defaultdict(list)\n",
    "        for i, like in enumerate(hats):\n",
    "            for a in like:\n",
    "                if a not in seen:\n",
    "                    seen[a] = m\n",
    "                    m += 1\n",
    "                h[seen[a]].append(i)\n",
    "        n = len(hats)\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(hats)\n",
    "        mx = max(max(hat) for hat in hats)\n",
    "        # 帽子可以带给谁\n",
    "        prefer = [[] for _ in range(mx + 1)]\n",
    "        for i,hat in enumerate(hats):\n",
    "            for h in hat:\n",
    "                prefer[h].append(i)\n",
    "        # idx：帽子编号\n",
    "        # mask：标记该people是否戴了帽子\n",
    "        @cache\n",
    "        def dfs(idx,mask) -> int:\n",
    "            # 所有人都带上了帽子\n",
    "            if mask == (1 << n) - 1:\n",
    "                return 1\n",
    "            # 枚举完所有帽子 此时还有人没戴帽子 不存在分配方案\n",
    "            if idx == mx + 1:\n",
    "                return 0\n",
    "            res = 0\n",
    "            res += dfs(idx + 1,mask)#不用该帽子\n",
    "            # 看该帽子给谁带\n",
    "            for p in prefer[idx]:\n",
    "                if (mask >> p) & 1 == 0:\n",
    "                    res += dfs(idx + 1,mask | (1 << p))\n",
    "            return res % MOD\n",
    "        \n",
    "        return dfs(1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        n = len(hats)\n",
    "        mask = (1 << n) - 1\n",
    "        MOD = int(1e9 + 7)\n",
    "        d = [set(x) for x in hats]\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if mask == 0:\n",
    "                return 1\n",
    "            if i == 0:\n",
    "                return int(mask == 0)\n",
    "            ans = dfs(i - 1,mask) % MOD\n",
    "            for j in range(n):\n",
    "                if mask >> j & 1 and i in d[j]:\n",
    "                    ans += dfs(i - 1,mask ^ (1 << j)) % MOD\n",
    "                    ans %= MOD\n",
    "            return ans \n",
    "\n",
    "        \n",
    "        return dfs(40,mask)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        m = len(hats)\n",
    "        graph = defaultdict(list)\n",
    "        for i , v in enumerate(hats):\n",
    "            for x in v:\n",
    "                graph[x].append(i)\n",
    "        \n",
    "        keys = list(graph.keys())\n",
    "        n = len(keys)\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,state):\n",
    "            if state == 0:\n",
    "                return 1\n",
    "            if i == n:return 0\n",
    "            ans = dfs(i+1,state)\n",
    "            for j in graph[keys[i]]:\n",
    "                if state & (1 << j):\n",
    "                    ans += dfs(i+1,state ^ (1 << j))\n",
    "            return ans % mod\n",
    "\n",
    "        return dfs(0,2**m - 1) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(hats)\n",
    "        mx = max(max(hat) for hat in hats)\n",
    "        # 帽子可以带给谁\n",
    "        prefer = [[] for _ in range(mx + 1)]\n",
    "        for i,hat in enumerate(hats):\n",
    "            for h in hat:\n",
    "                prefer[h].append(i)\n",
    "        # cnt：戴帽子人数\n",
    "        # idx：帽子编号\n",
    "        # mask：标记该people是否戴了帽子\n",
    "        @cache\n",
    "        def dfs(idx,mask) -> int:\n",
    "            # 所有人都带上了帽子\n",
    "            if mask == (1 << n) - 1:\n",
    "                return 1\n",
    "            if idx == mx + 1:\n",
    "                return 0\n",
    "            res = 0\n",
    "            res += dfs(idx + 1,mask)#不用该帽子\n",
    "            # 看该帽子给谁带\n",
    "            for p in prefer[idx]:\n",
    "                if (mask >> p) & 1 == 0:\n",
    "                    res += dfs(idx + 1,mask | (1 << p))\n",
    "            return res % MOD\n",
    "        \n",
    "        return dfs(1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        mod=10**9+7\n",
    "        dic=defaultdict(list)\n",
    "        n=len(hats)\n",
    "        for i in range(n):\n",
    "            for v in hats[i]:\n",
    "                dic[v].append(i)\n",
    "        \n",
    "        arr=[[i,v] for i ,v in dic.items()]\n",
    "        print(arr)\n",
    "\n",
    "        @cache\n",
    "        def dfs(cur,bitmask):            \n",
    "            if bitmask==2**n-1:\n",
    "                return 1\n",
    "            if cur==len(arr):return 0\n",
    "            \n",
    "            ans=0\n",
    "            ans+=dfs(cur+1,bitmask)\n",
    "            for i in arr[cur][1]:\n",
    "                if bitmask&(1<<i)==0:\n",
    "                    ans+=dfs(cur+1,bitmask|(1<<i))\n",
    "            return ans%mod\n",
    "\n",
    "        return dfs(0,0)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        # 人数 p\n",
    "        pn = len(hats)\n",
    "        h2p = [[] for _ in range(40)]\n",
    "        for i, ph in enumerate(hats):\n",
    "            for h in ph:\n",
    "                h2p[h - 1].append(i)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, s):\n",
    "            if s == (1 << pn) - 1:\n",
    "                return 1\n",
    "            if i == 40:\n",
    "                return 0\n",
    "\n",
    "            t = 0\n",
    "            for p in h2p[i]:\n",
    "                if (s>>p) & 1 == 0:\n",
    "                    t += dfs(i + 1, s | (1 << p))\n",
    "            t += dfs(i + 1, s)\n",
    "            return t\n",
    "\n",
    "        ans = dfs(0, 0)\n",
    "        ans %= MOD\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "\n",
    "        g = [[] for _ in range(40)]\n",
    "        for i, hat in enumerate(hats):\n",
    "            for h in hat:\n",
    "                g[h - 1].append(i)\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(hats)\n",
    "        tar = (1 << n) - 1\n",
    "        @cache\n",
    "        def dfs(idx, cur):\n",
    "            if cur == tar:\n",
    "                return 1\n",
    "            if idx == 40:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for p in g[idx]:\n",
    "                if not cur & 1 << p:\n",
    "                    res += dfs(idx + 1, cur | 1 << p)\n",
    "            res += dfs(idx + 1, cur)\n",
    "            return res % mod\n",
    "        return dfs(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "\n",
    "        g = [[] for _ in range(40)]\n",
    "        for i, hat in enumerate(hats):\n",
    "            for h in hat:\n",
    "                g[h - 1].append(i)\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(hats)\n",
    "        tar = (1 << n) - 1\n",
    "        @cache\n",
    "        def dfs(idx, cur):\n",
    "            if cur == tar:\n",
    "                return 1\n",
    "            if idx == 40:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for p in g[idx]:\n",
    "                if not cur & 1 << p:\n",
    "                    res += dfs(idx + 1, cur | 1 << p)\n",
    "            res += dfs(idx + 1, cur)\n",
    "            return res % mod\n",
    "        return dfs(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        n = len(hats)\n",
    "        mod = 1e9 + 7\n",
    "        d = defaultdict(list)\n",
    "        hsets = set()\n",
    "        for i, hs in enumerate(hats):\n",
    "            for h in hs:\n",
    "                d[h].append(i)\n",
    "                hsets.add(h)\n",
    "        hsets = sorted(list(hsets))\n",
    "        # 第i顶帽子，当前匹配状态st\n",
    "        @cache\n",
    "        def dfs(i, st):\n",
    "            if i < 0: return st == ((1 << n) - 1)\n",
    "            if st == ((1 << n) - 1): return 1\n",
    "            res = dfs(i-1, st) % mod # 帽子匹配人，可以选择当前帽子跳过\n",
    "            for p in d[hsets[i]]:\n",
    "                if st >> p & 1 == 0:\n",
    "                    res += dfs(i-1, st | (1 << p))\n",
    "                    res %= mod\n",
    "            return res\n",
    "        return int(dfs(len(hsets)-1, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        n = len(hats)\n",
    "        mod = 1e9 + 7\n",
    "        d = defaultdict(list)\n",
    "        hsets = set()\n",
    "        for i, hs in enumerate(hats):\n",
    "            for h in hs:\n",
    "                d[h].append(i)\n",
    "                hsets.add(h)\n",
    "        hsets = sorted(list(hsets))\n",
    "        # 第i顶帽子，当前匹配状态st\n",
    "        @cache\n",
    "        def dfs(i, st):\n",
    "            if i < 0: return st == ((1 << n) - 1)\n",
    "            if st == ((1 << n) - 1): return 1\n",
    "            res = dfs(i-1, st) % mod\n",
    "            for p in d[hsets[i]]:\n",
    "                if st >> p & 1 == 0:\n",
    "                    res += dfs(i-1, st | (1 << p))\n",
    "                    res %= mod\n",
    "            return res\n",
    "        return int(dfs(len(hsets)-1, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        n = len(hats)\n",
    "        mod = 1e9 + 7\n",
    "        d = defaultdict(list)\n",
    "        hsets = set()\n",
    "        for i, hs in enumerate(hats):\n",
    "            for h in hs:\n",
    "                d[h].append(i)\n",
    "                hsets.add(h)\n",
    "        hsets = sorted(list(hsets))\n",
    "        print(d)\n",
    "        print(hsets)\n",
    "        # 第i顶帽子，当前匹配状态st\n",
    "        @cache\n",
    "        def dfs(i, st):\n",
    "            if i < 0: return st == ((1 << n) - 1)\n",
    "            if st == ((1 << n) - 1): return 1\n",
    "            res = dfs(i-1, st) % mod\n",
    "            for p in d[hsets[i]]:\n",
    "                if st >> p & 1 == 0:\n",
    "                    res += dfs(i-1, st | (1 << p))\n",
    "                    res %= mod\n",
    "            return res\n",
    "        return int(dfs(len(hsets)-1, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        n = len(hats)\n",
    "        @cache\n",
    "        def fun(hatid, mask):\n",
    "            if mask == (1 << n)-1:\n",
    "                return 1\n",
    "            if hatid > 40:\n",
    "                return 0\n",
    "            res = fun(hatid+1, mask)\n",
    "            for i in range(n):\n",
    "                if not mask & (1 << i) and hatid in hats[i]:\n",
    "                    res += fun(hatid+1, mask | (1 << i))\n",
    "            return res\n",
    "        return fun(1, 0) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "       MOD = 10 ** 9 + 7\n",
    "       n = len(hats)\n",
    "       u = (1 << n) - 1\n",
    "       g = [[] for _ in range(41)]\n",
    "       for i in range(n):\n",
    "          for j in range(len(hats[i])):\n",
    "             g[hats[i][j]].append(i)\n",
    "       \n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if j == u:\n",
    "             return 1\n",
    "          if i == 41:\n",
    "             return 0\n",
    "          res = dfs(i + 1, j)\n",
    "          for k in g[i]:\n",
    "             if ((j >> k) & 1) == 0:\n",
    "                res += dfs(i + 1, j | (1 << k))\n",
    "                res %= MOD\n",
    "          return res\n",
    "       return dfs(1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        n = len(hats)\n",
    "        mod = 10**9+7\n",
    "        t = (1<<n) - 1\n",
    "        rec = defaultdict(list)\n",
    "        for k,v in enumerate(hats):\n",
    "            for h in v:\n",
    "                rec[h].append(k)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,state):\n",
    "            if state == t:\n",
    "                return 1\n",
    "            if i > 40:\n",
    "                return 0\n",
    "            ans = dfs(i+1,state)\n",
    "            for j in rec[i]:\n",
    "                if state >> j & 1 == 0:\n",
    "                    ans += dfs(i+1,state | 1 << j) % mod\n",
    "                # cand.add(v)\n",
    "            return ans % mod\n",
    "        return dfs(1,0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        d = defaultdict(list)\n",
    "        for index,v in enumerate(hats):\n",
    "            for i in v:\n",
    "                d[i].append(index)\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(hats)\n",
    "        @cache\n",
    "        def dfs(i,c):\n",
    "            if c == 2**n -1:\n",
    "                return 1\n",
    "            elif i > 40 :\n",
    "                return 0\n",
    "            # 不分配当前的帽子\n",
    "            res = dfs(i+1, c)\n",
    "            for p in d[i]:\n",
    "                # 尝试把帽子给这个人\n",
    "                if not c >> p & 1:\n",
    "                    res += dfs(i+1, c | (1 << p))\n",
    "            return res % mod\n",
    "        return dfs(1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        #尝试把帽子分给人\n",
    "        #状态压缩\n",
    "        n=len(hats)#n个人\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if i==41:\n",
    "                return 1 if mask==0 else 0\n",
    "            res=0\n",
    "            res+=dfs(i+1,mask)\n",
    "            for j in range(n):\n",
    "                if mask>>j&1 and i in hats[j]:\n",
    "                    #尝试分给第j个人\n",
    "                    res+=dfs(i+1,mask^(1<<j))\n",
    "            return res%MOD\n",
    "        return dfs(1,(1<<n)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        #尝试把帽子分给人\n",
    "        #状态压缩\n",
    "        n=len(hats)#n个人\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if i==41:\n",
    "                return 1 if mask==0 else 0\n",
    "            res=0\n",
    "            #当前帽子不分配\n",
    "            res+=dfs(i+1,mask)\n",
    "            #当前帽子分配,只是决定要分给谁\n",
    "            for j in range(n):\n",
    "                if mask>>j&1 and i in hats[j]:\n",
    "                    #尝试分给第j个人\n",
    "                    res+=dfs(i+1,mask^(1<<j))\n",
    "            return res%MOD\n",
    "        return dfs(1,(1<<n)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        #尝试把帽子分给人\n",
    "        #状态压缩\n",
    "        n=len(hats)#n个人\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if i==41:\n",
    "                return 1 if mask==0 else 0\n",
    "            res=0\n",
    "            res=(res+dfs(i+1,mask))%MOD\n",
    "            for j in range(n):\n",
    "                if mask>>j&1 and i in hats[j]:\n",
    "                    #尝试分给第j个人\n",
    "                    res=(res+dfs(i+1,mask^(1<<j)))%MOD\n",
    "            return res%MOD\n",
    "        return dfs(1,(1<<n)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        #尝试把帽子分给人\n",
    "        #状态压缩,将人的状态压缩\n",
    "        n=len(hats)#n个人\n",
    "        for i in range(n):\n",
    "            hats[i]=set(hats[i])\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if i==41:\n",
    "                return 1 if mask==0 else 0\n",
    "            res=0\n",
    "            #当前帽子不分配\n",
    "            res+=dfs(i+1,mask)\n",
    "            #当前帽子分配,只是决定要分给谁\n",
    "            for j in range(n):\n",
    "                if mask>>j&1 and i in hats[j]:\n",
    "                    #尝试分给第j个人\n",
    "                    res+=dfs(i+1,mask^(1<<j))\n",
    "            return res%MOD\n",
    "        return dfs(1,(1<<n)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        n = len(hats)\n",
    "        mod = 10 ** 9 + 7\n",
    "        d = defaultdict(list)\n",
    "        for i, hat in enumerate(hats):\n",
    "            for h in hat:\n",
    "                d[h - 1].append(i)\n",
    "        \n",
    "        tar = (1 << n) - 1\n",
    "        @cache\n",
    "        def dfs(idx, mask):\n",
    "            if mask == tar:\n",
    "                return 1\n",
    "            if idx == 40:\n",
    "                return 0\n",
    "            res = 0\n",
    "            res += dfs(idx + 1, mask)\n",
    "            for p in d[idx]:\n",
    "                if not mask & 1 << p:\n",
    "                    res += dfs(idx + 1, mask | 1 << p)\n",
    "            return res % mod\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        #尝试把帽子分给人\n",
    "        #状态压缩,将人的状态压缩\n",
    "        n=len(hats)#n个人\n",
    "        for i in range(n):\n",
    "            hats[i]=set(hats[i])\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if i==41:\n",
    "                return 1 if mask==0 else 0\n",
    "            res=0\n",
    "            #当前帽子不分配\n",
    "            res+=dfs(i+1,mask)\n",
    "            #当前帽子分配,只是决定要分给谁\n",
    "            for j in range(n):\n",
    "                if mask>>j&1 and i in hats[j]:\n",
    "                    #尝试分给第j个人\n",
    "                    res+=dfs(i+1,mask^(1<<j))\n",
    "            return res%MOD\n",
    "        return dfs(1,(1<<n)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberWays(self, hats: List[List[int]]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, state):#第i顶帽子,戴帽子人的状态\n",
    "            if state == 2 ** l - 1:#如果所有人都带了帽子\n",
    "                return 1\n",
    "            elif i > 40:#如果40顶帽子已经带完\n",
    "                return 0\n",
    "            res = dfs(i + 1, state)#不带本顶帽子\n",
    "            for j in d.get(i, []):#找到可以带帽子的人\n",
    "                if state >> j & 1 == 0:#如果当前此人未戴帽子\n",
    "                    res += dfs(i + 1, state | 1 << j)\n",
    "            return res % mod\n",
    "        l = len(hats)\n",
    "        d = {}#记录每顶帽子能被哪些人带上\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i, s in enumerate(hats):\n",
    "            for j in s:\n",
    "                if j not in d:\n",
    "                    d[j] = []\n",
    "                d[j].append(i)\n",
    "        return dfs(1, 0)\n",
    "\n",
    "# 作者：琴棋书画\n",
    "# 链接：https://leetcode.cn/problems/number-of-ways-to-wear-different-hats-to-each-other/solutions/1674944/python-zhuang-ya-dfs-by-qin-qi-shu-hua-2-sx8q/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
